package leetcode.sword;

import java.util.Stack;

public class Solution33 {
    public static void main(String[] args) {
        int[] arr = {5,4,3,2,1};
        Solution33 s = new Solution33();
        System.out.println(s.verifyPostorder1(arr));
    }
    public boolean verifyPostorder(int[] postorder) {
        return verify(postorder,0,postorder.length-1);
    }

    public boolean verify(int[] arr, int start, int end){
        if(start>=end) return true; //到叶子了
        int tmp=start;
        while(arr[tmp]<arr[end]) tmp++; //找到比end大的第一个元素下标
        //检查第一个比end大的元素后的元素是否都比end大
        for(int i=tmp+1;i<end;i++){
            if(arr[i]<arr[end]) {
                return false;
            }
        }
        //检查通过，对左右子树递归
        return verify(arr,start,tmp-1)&&verify(arr,tmp,end-1);
    }

    /**
     * 单调栈写法，复杂度O(n)
     */
    public boolean verifyPostorder1(int[] postorder) {
        Stack<Integer> stack = new Stack<Integer>();
        int curRoot = Integer.MAX_VALUE;
        for (int i = postorder.length-1; i >=0 ; i--) {
            int curNode = postorder[i]; //
            if(curNode>curRoot) return false;
            while (!stack.isEmpty()&&curNode<stack.peek()){ //把左子树和根节点出栈
                curRoot = stack.pop();
            }
            stack.push(curNode);
        }
        return true;
    }
}